/*
 * @lc app=leetcode.cn id=146 lang=golang
 *
 * [146] LRU 缓存
 */

// @lc code=start
type LRUCache struct {
	capacity int
	mp       map[int]*HNode
	head     *HNode
	tail     *HNode
	size     int
}
type HNode struct {
	Val  int
	Key  int
	Pre  *HNode
	Next *HNode
}

func Constructor(capacity int) LRUCache {
	head := &HNode{}
	tail := &HNode{}
	head.Next = tail
	tail.Pre = head

	return LRUCache{
		capacity: capacity,
		mp:       map[int]*HNode{},
		head:     head,
		tail:     tail,
		size:     0,
	}
}

func (this *LRUCache) Get(key int) int {
	if value, ok := this.mp[key]; ok {
		this.moveToHead(value)
		return value.Val
	} else {
		return -1
	}
}
func (this *LRUCache) moveToHead(value *HNode) {
	this.remove(value)
	this.addHead(value)
}
func (this *LRUCache) remove(value *HNode) {
	value.Pre.Next = value.Next
	value.Next.Pre = value.Pre
}
func (this *LRUCache) addHead(value *HNode) {
	value.Next = this.head.Next
	value.Pre = this.head

	this.head.Next.Pre = value
	this.head.Next = value
}
func (this *LRUCache) Put(key int, value int) {
	if this.capacity <= 0 {
		return
	}

	if v, ok := this.mp[key]; ok {
		v.Val = value
		this.moveToHead(v)
		return
	}

	this.size++
	if this.size > this.capacity {
		this.size--
		last := this.tail.Pre
		this.remove(last)
		delete(this.mp, last.Key)
	}
	node := &HNode{Key: key, Val: value}
	this.addHead(node)
	this.mp[key] = node
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */
// @lc code=end

